public class TTTSmartPlayer implements TTTPlayer
{
	// approach
	public static final int MINMAX = 0;
	public static final int ALPHABETA = 1;
	
	// stage 
	public static final int MAX = 1;
	public static final int MIN = 0;
	
	private int mode;
	private TTTBoard board;
	private int player;
	private int opp;
	
	private class Dmove extends TTTMove{
		private int value;
		
		public Dmove(int row, int col, int player){
			super(row,col,player);
			
		}
		
		public int getValue(){
			
			return value;
		}
		
		public void setValue(int value){
			this.value = value;
				
		}
		
	}
	
	

	// determine the searching approach
	public TTTSmartPlayer(int mode)
	{
		this.mode = mode;
		
		// You can implement this constructor, but it may not be necessary.
		//throw new RuntimeException("You must implement this method!");
	}
	
	
	public TTTMove getMove(TTTBoard board, int player)
	{
		this.board = board;
		this.player = player;
		if (player == board.PLAYER_1)
			this.opp = board.PLAYER_2;
		else
			this.opp = board.PLAYER_1;
		
		
		if (mode == MINMAX){
			Dmove returnDmove = miniMax(new Dmove(0,0,player),MAX);
			return new TTTMove(returnDmove.getRow(),returnDmove.getCol(),player);
		}
		else if (mode == ALPHABETA){
			ReturnValue rv = alphaBeta(-2,2,MAX);
			return new TTTMove(rv.row,rv.col,player);
		}
		else{
			throw new RuntimeException("got a unknow mode type at getMove function");
		}
		//throw new RuntimeException("You must implement this method!");
	}
	
	/**
	 *  miniMax will use brute force to DFS all the possible result
	 * @param row --- row of current stat 
	 * @param col
	 * @param player
	 * @return
	 */
	public Dmove miniMax(Dmove move, int stage){
		
		//check the input validation
		/* must be one of the players
		if (move.getPlayer() != board.PLAYER_1 && move.getPlayer() != board.PLAYER_2){
			System.out.println("must be one of the players!");
			System.exit(-1);
		}*/
		
		/* validate input and col
		if (move.getRow() < 0 || move.getRow() >= board.getRows() || move.getCol() < 0 || move.getCol() >= board.getCols()){
			System.out.println("miniMax searching out of board");
			System.exit(-1);
		}*/
		
		
		
		
		
		// Base Case
		// apply the move to see whether we got the final result
		//board.applyMove(move);
		if ( board.gameIsOver()){
			
			int winner;
			
			// need some translation
			if (player == board.PLAYER_1)
				 winner = board.winner;
			else{
				switch(board.winner){
					case 1: winner = -1;break;
					case -1: winner = 1;break;
					default: winner = board.winner;
				}
			}
			move.setValue(winner);
			
			
			// need to restore to make no affects to the board
			//board.undoMove(move);
			
			//System.out.println("game over: winner:"+move.getValue()+"coonds: "+move.getRow()+move.getCol());
			return move;
		}
		
		// Recursive Case
		// setup a return value
		// for Max
		Dmove moveV; 
		if (stage == MAX){
			moveV = new Dmove(1,1,move.getPlayer());
			moveV.setValue(-2);
		}	
		//for Min
		else {
			moveV = new Dmove(0,0,move.getPlayer());
			move.setValue(2);
		}
			
		
			
		// could be optimized
		for (int row=0; row < board.getRows(); row++){
			for (int col=0; col < board.getCols(); col++){
				// kick out the occupied position
				if (board.getBoardData(row, col) != board.EMPTY)
					continue;
				
				
				Dmove newMove = null;
				// Max stage
				if (stage == MAX){
					newMove = new Dmove(row, col, player);
					board.applyMove(newMove);
					Dmove returnMove = miniMax(newMove,MIN);
					if (returnMove.getValue() > moveV.getValue()){
						moveV = newMove;	
						moveV.setValue(returnMove.getValue());
					}	
				}
				
				// Min stage
				if (stage == MIN){
					newMove = new Dmove(row, col, opp);
					board.applyMove(newMove);
					Dmove returnMove = miniMax(newMove,MAX);
					if (returnMove.getValue() < moveV.getValue()){
						moveV = newMove;
						moveV.setValue(returnMove.getValue());
					}
				}
				board.undoMove(newMove);			
				
			}
		}
		
		
		///////////////////////////////////////////////////////////
		//System.out.println("return result");
		return moveV;
	}
	
	
	
	
	
	
	// alphaBeta algorithm 
	
	private class ReturnValue{
		int row = -10;
		int col = -10;
		int value = 0;
	}
	
	private ReturnValue alphaBeta(int a, int b, int stage){
		
		//throw new RuntimeException("You must implement this method!");
		// setup a alpha beta variables
		int alpha = a;
		int beta = b;
		
		// initial return variable
		ReturnValue rv = new ReturnValue();
		
		// Base case:
		// base case will be find the game is over!!! same as minimax algorithm
		if (board.gameIsOver()){

			int winner;
			
			// need some translation
			if (player == TTTBoard.PLAYER_1)
				 winner = board.winner;
			else{
				switch(board.winner){
					case 1: winner = -1;break;
					case -1: winner = 1;break;
					default: winner = board.winner;
				}
			}	
			rv.value = winner;
			return rv;
		}
		
		/////////////////////////////////////////////////////
		
			
			
		// define 1 pointer for the loop
		TTTMove currMove = null;
		
		// Recursive case:
		for (int row=0; row < board.getRows(); row++){
			for (int col=0; col < board.getCols(); col++){
				// kick out the occupied position
				if (board.getBoardData(row, col) != TTTBoard.EMPTY)
					continue;
				
				// for MAX stage
				if (stage == MAX){
					currMove = new TTTMove(row,col,player);
					board.applyMove(currMove);
					ReturnValue tmp = alphaBeta(alpha, beta, MIN);
					// recover 
					board.undoMove(currMove);
					
					// then, update alpha
					if ( tmp.value > alpha ){
						rv.row = row;
						rv.col = col;
						alpha = tmp.value;
						rv.value = alpha;
					}
					
					// first pruning
					if ( tmp.value >= beta ){
						return rv;
					}	
					//
				}
				
				// for MIN stage
				if (stage == MIN){
					currMove = new TTTMove(row,col,opp);
					board.applyMove(currMove);
					ReturnValue tmp = alphaBeta(alpha, beta, MAX);
					// recover 
					board.undoMove(currMove);
					// then, update beta
					if ( tmp.value < beta){
						rv.row = row;
						rv.col = col;
						beta = tmp.value;
						rv.value = beta;
					}
					
					// first pruning
					if ( tmp.value <= alpha){
						return rv;
					}
					//	
					
				}
					
				
			}
		}
		
		// no pruning???
		return rv;
		/////////////////////////////////////////////////////
	}
	
}
